1. Field of the Invention
This invention relates to a cryptographic key recovery system and, more particularly, to a method and apparatus for interoperable validation of the correctness of key recovery information within a cryptographic system.
2. Description of the Related Art
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories. Symmetric (or private key) encryption systems such as the Data Encryption Standard (DES) system use the same secret key for both encrypting and decrypting messages. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir and Adleman.
Asymmetric encryption systems are generally more computationally intensive than symmetric encryption systems, but have the advantage that they do not require a secure channel for the transmission of encryption keys. For this reason, asymmetric encryption systems are often used for the one-time transport of highly sensitive data such as symmetric encryption keys.
Data encryption systems of all types have attracted the attention of government intelligence agencies and law enforcement agencies, since the same cryptographic strength that prevents decryption by unauthorized third parties also prevents decryption by intelligence or law enforcement officials having a legitimate reason for wanting to access the plaintext data. Because of such concerns, governments have either prohibited the use or export of strong encryption systems or have conditioned their approval on the use of weakened keys that are susceptible to key-exhaustion attacks (i.e., systematically testing all possible keys until the right one is found). Such weak encryption systems have the obvious disadvantage that they are just as vulnerable to unauthorized third parties as they are to authorized government officials.
Various cryptographic key recovery systems have recently been proposed as a compromise between the demands of communicating parties for privacy in electronic communications and the demands of law enforcement agencies for access to such communications when necessary to uncover crimes or threats to national security. Generally, in such key recovery systems, all or part of the key used by the communicating parties is made available to one or more key recovery agents, either by actually giving key related recovery information to the key recovery agents ahead of time, (in which case the recovery information is said to be "escrowed") or by providing sufficient information in the communication itself (as by encrypting the key portions) which the key recovery agents could obtain after the communication occurred. Key recovery agents would reveal the escrowed or regenerated key information to a requesting law enforcement agent only upon presentation of proper evidence of authority, such as a court order authorizing the interception. The use of multiple key recovery agents, all of which must cooperate to recover the key, minimizes the possibility that a law enforcement agent can improperly recover a key by using a corrupt key recovery agent.
Key recovery systems serve the communicants' interest in privacy, since their encryption system retains its full strength against third parties and does not have to be weakened to comply with domestic restrictions on encryption or to meet export requirements. At the same, key recovery systems serve the legitimate needs of law enforcement by permitting the interception of encrypted communications in circumstances where unencrypted communications have previously been intercepted (as where a court order has been obtained).
In addition to serving the needs of law enforcement, key recovery systems find application in purely private contexts. Thus, organizations may be concerned about employees using strong encryption of crucial files where keys are not recoverable. Loss of keys may result in loss of important stored data.
An important aspect of key recovery systems is the method used to ensure that correct recovery information is provided. If the recovery information provided is not correct, either through unintentional error, or deliberate attempt to corrupt, the functionality of the key recovery system can be thwarted. Validation can be provided in several ways, including direct checking by the participants, checking by the recovery agents, and checking by the recovery entity. Correctness can also be ensured by redundant calculation and disclosure of the recovery information by more than one of the communicating parties.
One of the problems with implementing cryptographic systems and the application programs that use the cryptographic systems is the large number of differing cryptographic methods and the rate of development of new methods. An important technique to simplify and standardize cryptographic support for applications is the concept of a software framework. A framework separates a given function into one part which is common across all specific methods, and multiple smaller modules which are specific to given methods. Different or new specific modules can replace or extend functionality, by "plugging" them into the framework, without having to update any applications.
To keep application writers from having to rewrite their code for each different cryptographic method and for every change in a given method, several cryptographic frameworks have been proposed, such as Microsoft's CAPI, and Intel's CDSA. The basic concept of the framework is to provide a consistent Application Programming Interface (API) to the application, under which the framework may plug any of a number of possible Cryptographic Service Provider (CSP) modules. These frameworks allow all application writers, and all writers of CSP methods to write to a common standard interface. The framework is designed to be very abstract and generic, so that any CSP representing possibly new cryptographic methods can be accommodated in the future, without having to update the applications using the framework.
It is possible to add key recovery functionality to an application that uses a cryptographic framework, by modifying the framework to support the adding of Key Recovery Service Provider (KRSP) modules. Just as the CSP would provide encryption and key exchange services to the application in a transparent, flexible manner, a KRSP would transparently enable the key recovery functionality, by creating the necessary key recovery information for a given key. The framework would place the key recovery information into the cryptographic data, so that actual key recovery (at some later time) would be enabled.
More generally, the framework would place the key recovery information into the "appropriate place" wherever that might be. It might be integrated into the transmitted or stored data, it might be integrated into key transport or key agreement protocol, it might be stored in a separate escrow file. It might be sent over a completely different channel, e.g., to a node that maybe just tosses it away.
In a similar manner, an application which provides the key recovery service (based on the key recovery information embedded by the enabling framework), may itself be layered on top of a Key recovery Service framework. A Key Recovery Service Service Provider (KRSSP) would plug into the framework, and perform actual key recovery calculations on a given set of key recovery data.
Key recovery systems of various types are described in D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow Encryption Systems", Communications of the ACM, vol. 39, no. Mar. 3, 1996, pp. 34-40, incorporated herein by reference. Several specific key recovery systems are noted below.
Micali et al. U.S. Pat. No. 5,276,737 ("Micali I") and U.S. Pat. No. 5,315,658 ("Micali II") describe a "fair" public key cryptosystem in which the private key of a public/private key pair is broken into "shares" that are given to "trustees". The "breaking" is done in such a manner that: (1) the shares of all trustees (or a predetermined quorum) are required to reconstruct the key; and (2) each trustee can individually verify the correctness of his share. When all the trustees have certified the correctness of their share, the user's public key (corresponding to the escrowed private key) is certified by a key management center. Upon a predetermined request, the trustees provide their shares to a law enforcement agent or other recovering entity, who then reconstructs the private key from the shares and, with the private key, is able to monitor communications to the user. In this key recovery system, verification is done by the key management center and the trustees. This method of verification is undesirable, in that it requires prior communications with the trustees and key management center.
In another key recovery system, described in U.S. Pat. No. 5,557,346 to Lipner et al., the sender splits a session key into first and second session key portions by setting the first session key portion equal to a random number and setting the second session key portion equal to the XOR product of the random number and the session key. The sender creates a law enforcement access field (LEAF) by encrypting the respective session key portions with the public encryption keys of first and second key recovery agents and concatenating the two encryption products. The sender also creates a LEAF verification string (LVS) by concatenating the original session key portions and encrypts this using the session key to form an encrypted LEAF verification string (ELVS). Finally, the sender transmits an encrypted message, together with the LEAF and ELVS, to the receiver.
Before decrypting the encrypted message, the receiver regenerates the LEAF to verify that the sender has created a proper LEAF that would actually permit recovery of the session key through the key recovery agents. This is done by decrypting the ELVS to obtain the session key portions and then encrypting the respective session key portions with the public encryption keys of first and second key recovery agents. If the receiver succeeds in regenerating the transmitted LEAF in this manner, it concludes that the LEAF is genuine and proceeds to decrypt the message. Otherwise, it concludes that the LEAF is corrupt and does not proceed with the decryption step.
In this key recovery system, the verification of key recovery information is done by the receiver, which does avoid communication with the trustees or key management center. It does however require several public key encryption and decryption operations for every communication session, which is expensive in terms of computation and message size.
The copending application of R. Gennaro et al., Ser. No. 08/725,102, filed Oct. 2, 1996, and entitled "Two- Phase Cryptographic Key Recovery System", describes an alternative method of key recovery, called SKR, which permits a portion of the key recovery information to be generated once and then used for multiple encrypted data communications sessions and encrypted file applications. In particular, the mentioned portion of the key recovery information that is generated just once is the portion that requires public key encryption operations. Hence, SKR provides a way of reducing the costly public key encryption operations required of other key recovery methods.
The Gennaro et al. application also describes a verification mode in which the communicating parties Alice and Bob each produce SKR recovery blocks independently, without checking the other's so produced blocks. In this mode, if at least one side is correctly configured, all required recovery information is correctly produced. In addition, both Alice and Bob are free to include any optional recovery fields without causing a false invalidation of what the other sent. One limitation of this verification mode, however, is that it is not always convenient to establish bidirectional data connections, so this method of verification may be undesirable for some applications, such as store and forward electronic mail.
The SKR method of key recovery and verification described in the Gennaro et al. application is computationally efficient, as it provides for extensive caching of the recovery information, and requires no explicit verification. Its principal disadvantages are: (1) that it does not provide verification for non-interactive communications without requiring the receiver to perform public key operations; and (2) that it requires the transmission of additional secret information to Bob to allow him to perform verification, increasing the size of required communications.
The recent paper of E. Verheul, B.-J. Koops and H. C. A. van Tilborg entitled "Binding Cryptography: A Fraud-Detectible Alternative to Key-Escrow Proposals" (1996), published at http://cwis.kub.nl/.about.frw/people/koops/binding.htm, and the paper of E. Verheul and H. C. A. van Tilborg entitled "Binding the ElGamal Encryption Scheme" (1996), published at http://cwis.kub.nl/.about.frw/people/koops/bindtech.htm, present an alternative for verification of key recovery information. The papers describe a method in which a disinterested observer can verify that something encrypted under a receiver's public key is the same as something encrypted under an agent's public key. If the "something" is a session key or part of a session key, as is the case in key recovery fields, the observer can use this to validate the encrypted recovery data. Unlike the previous methods of verification, however, this method provides no way for the observer to verify that the encrypted fields actually contain correct information; instead, the observer only verifies that the encryptions contain the same secret.
Still other methods of verifiably providing key recovery use variants of the Diffie-Hellman (DH) key agreement protocol. By way of background, the Diffie-Hellman key agreement protocol is a procedure whereby two parties may establish a shared secret value (from which a symmetric encryption key may be derived) by exchanging only public values over a communications channel. The protocol was originally described at page 649 of W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol. IT-22, no. 6, November 1976, pp. 644-654, and in U.S. Pat. No. 4,200,770, both incorporated herein by reference.
In the two-party interactive form of the protocol, each party generates (e.g., pseudorandomly) a secret value x which it keeps to itself. Each party then generates a public value EQU y=g.sup.x mod p
where x is the secret value of that party, p is a prime modulus and g is a generator over the Galois field GF(p), and transmits the public value to the other party. Thereafter, each party generates a shared secret value EQU z=y.sup.x mod p
where x is its own secret value, y is the public value received from the other party, and p is defined as above. By virtue of the properties of modulo arithmetic, the shared secret values z generated by the two parties are the same.
The parties may derive a symmetric encryption key directly from the shared secret value z, as by extracting the required number of bits. Alternatively, the parties may perform a further operation on the shared secret value such as concatenating it with another value and hashing the concatenation result, as described in the copending application of S. M. Matyas et al., Ser. No. 08/736,774, filed Oct. 25, 1996, entitled "Method and Apparatus for Establishing an Authenticated Shared Secret Value Between a Pair of Users", incorporated herein by reference.
The security of this procedure relies on the apparent fact that, for appropriate choices of p and g, it is computationally infeasible to obtain either the secret values x or the shared value z from the public values y exchanged between the parties. Although exponentiation over a finite field was used in the above example, in general any suitable functions y(x) and z(x,y) may be used that have the commutative property EQU z(x.sub.1,y(x.sub.2))=z(x.sub.2, y(x.sub.1))
for any x.sub.1 and x.sub.2 and have the noninvertibility property mentioned above.
One such method of verifiably providing key recovery based on establishing a shared common Diffie-Hellman key was proposed by Dorothy E. Denning in "To Tap or Not to Tap", Communications of the ACM, vol. 36, no. 3, March 1993, pp. 26-33. In this paper she proposed an escrow system based on a three-party variation of Diffie-Hellman described in section 22.1 of B.
Schneier, Applied Cryptography (2d ed. 1996) as well as in the original Diffie et al. (1976) article cited above. In this method of key recovery, the verification of the recovery information can be inherent in the receiver's decryption of the information encrypted under the shared session key k.
The system proposed by Denning works as follows: Let Alice be the sender, Bob be the receiver, and Ted the trustee in order around the three-party circle. Let their respective secret parts be x, y, and z. In the first round, Alice sends to Bob g.sup.x mod p, Bob sends to Ted g.sup.y mod p, and Ted sends to Alice g.sup.z mod p. In the second round, Alice sends to Bob g.sup.zx mod p, Bob sends to Ted g.sup.xy mod p, and Ted sends to Alice g.sup.yz mod p. From these values, everyone can calculate k=g.sup.xyz. If Alice sends something to Bob encrypted with k, Bob knows that Ted can calculate k and decrypt it also. (If Alice is dishonest, and does not want Ted to be able to calculate k correctly she could send an incorrect value of g.sup.zx mod p to Bob, and Bob would be unable to detect the error.
This can be fixed by having Bob verify this value directly with Ted as an additional exchange of messages after the second round.)
This method has the advantage of being able to send encrypted recovery information to both Bob and Ted with a single encrypted field, thus reducing the size of data and the number of calculations. However, this method has the disadvantage of requiring communication with the trustee prior to transmission of the message to the receiver.
In a paper entitled "Alternatives to RSA Using Diffie-Hellman with DSS" (1996), published at http://www.cylink.com/products/security/rsa/rsa-dss2.htm, Cylink Corporation proposed a method similar to Denning's, but not requiring interactive communication with the trustee. Using the same example, let Alice be the sender, Bob be the receiver, and Ted be the trustee, and let their respective secret parts be x, y, and z.
Prior to any communication, Ted calculates a shared Diffie-Hellman key v with Alice based on Alice's public key (g.sup.x mod p), and his private key z, as follows: EQU u=g.sup.xz mod p EQU v=g.sup.u mod p
Ted publishes v as a public key shared between Alice and him. For communication with Bob, Alice can calculate a key k as: EQU k=g.sup.yv mod p
Both Bob and Ted can calculate k, so if Alice sends something to Bob encrypted with k, she knows that Ted can also read it. In addition, Bob can verify this escrow, as he knows that Ted published the shared key v, and Ted can therefore calculate k. However, the disadvantage of this method is that it requires Alice to obtain a published shared key from Ted prior to communication with Bob.
The copending application of R. Gennaro et al., Ser. No. 08/775,348, filed Jan. 3, 1997, entitled "Method and Apparatus for Verifiably Providing Key Recovery in a Cryptographic System", presents a method of verification of key recovery information within a key recovery system, based on a variation of the three-party Diffie-Hellman key agreement procedure. Without communication with a trustee, the sender is able to encrypt recovery information in such a way that both the receiver and the respective trustee can decrypt it. This reduces the number of encryptions, and inherently validates the recovery information when the receiver decrypts it. The method is compatible with interactive and non-interactive communication. In the non-interactive case, the parties all use long term, certified, public keys, which precludes perfect forward secrecy. In the interactive case, the sender and receiver can use authenticated ephemeral keys, which preserves perfect forward secrecy. The method allows full caching of all public key operations, thus further reducing computational overhead.
Note that while Diffie-Hellman is used to describe this method, any public key method with commutative common key agreement properties may be used. While RSA does not have this property, versions of elliptic curve encryption do have this property, and can directly use this method for deriving shared keys.
For the simplified description of the design, consider the case in which Alice is sending an encrypted message to Bob, and wants to provide key recovery information that can be read by Ted. (A more detailed design, handling multiple parties and agents will be provided below.) Let Alice, Bob and Ted have the respective DH keypairs {x, g.sup.x mod p}, {y, g.sup.y mod p}, {a, g.sup.a mod p}, where the public components (g.sup.x mod p, g.sup.y mod p, g.sup.a mod p) are known to all parties.
At any time, both Alice and Bob can calculate the following: EQU u=g.sup.xy mod p (their common key) EQU {u, g.sup.u } mod p (a new DH keypair shared between Alice and Bob) EQU v=g.sup.au mod p (a new common key between Alice-Bob and Ted)
Alice then picks a session key K which will be used to encrypt the message, and sends to Bob:
v(K) PA1 g.sup.u PA1 K(message)
where the expression v(K), for example, indicates symmetric encryption of K under the key v.
The first part includes the symmetric encryption under v of K. This field can be decrypted by Bob, who can calculate v from Ted's public key g.sup.a, and u. Ted can also decrypt the field, based on the included g.sup.u in the message, and his secret a. Thus the field v(K) serves both as secure transmission of K to Bob and as recovery information for Ted.
Note that all expensive public key calculations (the exponentiations) depend only on the secret values x, y, and a (for Alice, Bob, and Ted respectively). These values may be as long lived or as short lived as desired, trading off computation expense for greater security. In the non-interactive case, the values will typically be long lived, with the public components distributed as certificates. In this case there is no perfect forward secrecy, but all exponentiations are constant, and therefore need only be calculated once, and the results saved, providing significant reduction in computational overhead. In the interactive case, if perfect forward secrecy is desired, Alice and Bob can exchange ephemeral DH keys. This provides greater security, at the expense of having to perform all of the exponentiations for each session. In the interactive case, new values may be calculated at any desired frequency.
In all cases, it is assumed that the obtained Diffie-Hellman public keys have been validated (i.e., authenticated as actually originating from the person purporting to be the owner). Long-lived keys will typically be distributed as certificates whose signatures can be validated. In the case of ephemeral Diffie-Hellman keys, it is assumed that the ephemeral key exchange has been signed by certified keys in some way. The exact method of validation of these ephemeral keys is application dependent. One such method is described in the copending application of S. M. Matyas et al., Ser. No.08/736,774, referred to above.
The latter copending Gennaro et al. application of provides several desirable features. It provides the ability to cache all public key operations, and can be used in the interactive and non-interactive cases. It serves as a vehicle for transmission both to Bob and to the recovery agent, saving encryptions. Since it uses only published public keys, no additional keys need be exchanged. It can preserve perfect forward secrecy in the interactive case, if Alice and Bob exchange ephemeral g.sup.x and g.sup.y for every new session. Finally, it preserves the verification by both Alice and Bob: if Alice is honest, she correctly uses the agent's g.sup.a ; if Bob is honest, he inherently verifies that v is correctly based on g.sup.a.
The preceding verification methods all assume that the verifying party is able to interpret and verify the recovery information. There are many different key recovery algorithms, each producing a key recovery block (KRB) composed of different information using a uniquely different block format, including those described above, and it may be impractical for a receiver to be able to verify all of the possible formats. What is needed is an interoperable validation scheme in which a receiver may more easily establish some level of trust in the supplied recovery information.
Interoperable validation methods have several desirable properties. The validation method must support interoperability between all key recovery methods. The validation method should not require communication during message creation and transmission. The validation method should minimize the required computations, and transmission overhead associated with the validation.
If the receiver is unable to verify a given KRB directly, the next best approach is to validate the sender's cryptographic framework. For example, the sender could attempt to prove that it is a valid IBM framework implementation. The receiver could accept such proof as evidence that the given KRB must be correct.
One approach to providing such a proof would be for the sending framework code to sign the KRB with a private key known only to a "good" implementation. The receiver could verify the signature with the corresponding public key certificate. However, there are several potential problems with this signature approach.
First, the private key needs to be made available to the framework code in some way. If a single private key is used for all copies shipped, and if this private key is ever extracted from the code, then all copies would be compromised. If each copy shipped is given a different private key, then there is the difficulty of branding each copy (quite difficult with CD-ROMs), and also the difficulty of setting up the associated certificate authority (CA) service, so that the receiver can verify a signature's corresponding public key.
Second, software-only solutions cannot securely hide a private key; it is only a matter of time until someone posts a tool for extracting a given key in such a system. If the private keys are exposed, then bad senders could easily impersonate a good sender, while providing bogus key recovery information.